package org.yh.algorithm;

/**
 * @Author: yh
 * @Description:快速排序
 * @Date: Created in 9:42 2019/5/22
 * @Modified By:
 */
public class QuickSort {


    /**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     */
    public void quicksort(int arr[], int left, int right) {
        if (left >= right) {
            return;
        }
        int init_left = left;
        int init_right = right;
        //以数组的第一个数为基准
        int start = arr[left];
        while (left != right) {
            //找到右边比左边小的数，交换位置
            while (left < right && arr[right] >= start) {
                right--;
            }
            //交换
            arr[left] = arr[right];
            arr[right] = start;
            //此时从左边开始，找到大于基准值的值，交换位置
            while (left < right && arr[left] <= arr[right]) {
                left++;
            }
            arr[right] = arr[left];
            arr[left] = start;
        }
        System.out.println("节点值：" + left);
        System.out.println("排序结果：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        quicksort(arr, init_left, left - 1);
        quicksort(arr, right + 1, init_right);
    }


    public static void main(String[] args) {
        QuickSort q = new QuickSort();
        int arr[] = {3, 4, 12, 42, 7, 0, 8, 43};
        q.quicksort(arr, 0, arr.length - 1);
    }
}
